public class Solution3 {
    //494. 目标和
    public int findTargetSumWays(int[] nums, int target) {


        int n = nums.length;

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum + target) % 2 != 0 || (sum + target) < 0) {
            return 0;
        }
        int a = (sum + target) / 2;

        int[][] dp = new int[n+1][a+1];
        dp[0][0] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < a + 1; j++) {
                dp[i][j] += dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }

            }
        }
        return dp[n][a];
    }
}
